package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了99.00%的用户
 */
var ans []string
var strs = []string{
	"", "", "abc", "def",
	"ghi", "jkl", "mno",
	"pqrs", "tuv", "wxyz",
}

func letterCombinations(digits string) []string {

	ans = []string{}
	if len(digits) == 0 { return ans }
	dfs(digits, 0, "")
	return ans
}

func dfs(digits string, u int, path string) {
	if u == len(digits) {
		ans = append(ans, path)
	} else {
		for _, c := range strs[digits[u] - '0'] {
			dfs(digits, u + 1, path + string(c))
		}
	}
}

func main() {
	fmt.Println(letterCombinations("23"))
}
